package com.desin.modle.datastruct.stack;

import com.sun.jmx.remote.internal.ArrayQueue;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Stack;

/**
 * 堆栈
 */
public class MyStack {


    /**
     * 20. 有效的括号
     *
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
     *
     * 有效字符串需满足：
     *
     *     左括号必须用相同类型的右括号闭合。
     *     左括号必须以正确的顺序闭合。
     *
     * 注意空字符串可被认为是有效字符串。
     *
     * 输入: "()[]{}"
     * 输出: true
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/valid-parentheses
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        char[] chars = s.toCharArray();
        Map<Character,Character> map = new HashMap<Character, Character>();
        map.put(')','(');
        map.put(']','[');
        map.put('}','{');
        Stack<Character> stack = new Stack<Character>();
        for(Character character : chars){
            if(!map.containsKey(character)){
                stack.add(character);
            }else if(stack.isEmpty()||map.get(character)!=stack.pop()){
                return false;
            }

        }

        return stack.isEmpty();

    }

    /**
     * 232. 用栈实现队列
     *
     * 使用栈实现队列的下列操作：
     *
     *     push(x) -- 将一个元素放入队列的尾部。
     *     pop() -- 从队列首部移除元素。
     *     peek() -- 返回队列首部的元素。
     *     empty() -- 返回队列是否为空。
     *
     * MyQueue queue = new MyQueue();
     *
     * queue.push(1);
     * queue.push(2);
     * queue.peek();  // 返回 1
     * queue.pop();   // 返回 1
     * queue.empty(); // 返回 false
     *
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/implement-queue-using-stacks
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    class MyQueue {
        private Stack<Integer> input = new Stack<Integer>();
        private Stack<Integer> output = new Stack<Integer>();
        /** Initialize your data structure here. */
        public MyQueue() {

        }
        /** Push element x to the back of queue. */
        public void push(int x) {
            input.push(x);
        }
        /** Removes the element from in front of queue and returns that element. */
        public int pop() {
            if(!output.isEmpty()){
                return output.pop();
            }else {
                while (!input.isEmpty()){
                    output.push(input.pop());
                }
            }
            return output.pop();
        }
        /** Get the front element. */
        public int peek() {
            if(!output.isEmpty()){
                return output.peek();
            }else {
                while (!input.isEmpty()){
                    output.push(input.pop());
                }
            }
            return output.peek();
        }
        /** Returns whether the queue is empty. */
        public boolean empty() {
            return input.isEmpty()&&output.isEmpty();

        }
    }


    /**
     * 225. 用队列实现栈
     *
     *
     * 使用队列实现栈的下列操作：
     *
     *     push(x) -- 元素 x 入栈
     *     pop() -- 移除栈顶元素
     *     top() -- 获取栈顶元素
     *     empty() -- 返回栈是否为空
     *
     * 注意:
     *
     *     你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
     *     你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
     *     你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。
     *
     */
    class MyStackQueue {
        private LinkedList<Integer> queue = new LinkedList<Integer>();

        /** Initialize your data structure here. */
        public MyStackQueue() {

        }

        /** Push element x onto stack. */
        public void push(int x) {
            queue.add(x);
            int size = queue.size();
            while (size>1){
                queue.add(queue.remove());
                size--;
            }
        }

        /** Removes the element on top of the stack and returns that element. */
        public int pop() {
           return queue.remove();
        }

        /** Get the top element. */
        public int top() {
           return queue.peek();
        }

        /** Returns whether the stack is empty. */
        public boolean empty() {
            return queue.isEmpty();
        }
    }

    public Boolean checkkuohao(String str){
        if(str==null||str.length()==0){
            return false;
        }
        char[] arr = str.toCharArray();
        Map<Character,Character> map = new HashMap<>();
        map.put(')','(');
        map.put(']','[');
        map.put('}','{');
        Stack<Character> stack = new Stack<>();
        for(char c:arr){
            if(!map.containsKey(c)){
                stack.push(c);
            }else{
                if(stack.isEmpty()||map.get(c)!=stack.pop()){
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}
